#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<algorithm>
#include<limits>
#include <stack>
#include<iostream>
#include<sstream>
#include<deque>
#include<queue>
#include<set>
#include<unordered_set>
#define MOD 1000000007
class Solution {
public:
    int fill;
    int minAbsDifference(std::vector<int>& nums, int goal) {
        int n = nums.size();
        int zsum=0;
        int fsum = 0;
        for (int i = 0; i < n; i++)
        {
            if (nums[i] > 0)
            {
                zsum += nums[i];
            }else
            {
                fsum += nums[i];
            }
           
        }
        if (goal > zsum)
        {
            return std::abs(goal - zsum);
        }
        if (goal < fsum)
        {
            return fsum - goal;
        }

        std::sort(nums.begin(), nums.end());
        std::vector<int> left(1<<20);
        std::vector<int> right(1<<20);
        int edge = n/2;
        fill = 0;
        collect(nums,0,0,edge,left);
        int ll = fill;
        fill=0;
        collect(nums,edge,0,n,right);
        int lr = fill;
        std::sort(left.begin(), left.begin()+ll);
        std::sort(right.begin(), right.begin()+lr);
        int res = std::numeric_limits<int>::max();
        for (int i=0,j=lr-1;i<ll;i++)
        {
            while (j>0&&std::abs(right[j-1]+left[i]-goal)<=std::abs(left[i]+right[j]-goal))
            {
                j--;
            }
            res = std::min(res,std::abs(right[j]+left[i]-goal));
        }
        return res;
    }
    void collect(const std::vector<int>& nums, int i,int sum,int e,std::vector<int>& ans )
    {
       if (i==e)
       {
           ans[fill++] = sum;
       }else
       {
           int j = i+1;
           while (j<e&&nums[j] == nums[i])
           {
               j++;
           }
           for (int k=0;k<=j-i;k++)
           {
               collect(nums,j,sum+nums[i]*k,e,ans);
           }
       }
    }
};
